This file was created with JabRef 2.2.
Encoding: GBK

@ARTICLE{AKI87,
  author = {Hiroyuki Adachi and Hiroyuki Kamekawa and Shigeki Iwata},
  title = {Shogi on $n \times n$ Board is Complete in Exponential Time (in {J}apanese)},
  journal = {Transactions of the IEICE},
  year = {1987},
  volume = {J70-D},
  pages = {1843--1852},
  number = {10},
  month = {October}
}

@BOOK{All87,
  title = {Foundations of Analysis over Surreal Number Fields},
  publisher = {North-Holland Publishing Co.},
  year = {1987},
  author = {Norman Alling},
  address = {Amsterdam}
}

@ARTICLE{Arc99,
  author = {Aaron F. Archer},
  title = {A modern treatment of the 15 puzzle},
  journal = {American Mathematical Monthly},
  year = {1999},
  volume = {106},
  pages = {793--799},
  number = {9}
}

@BOOK{Bea85,
  title = {The Ins \& Outs of Peg Solitaire},
  publisher = {Oxford University Press},
  year = {1985},
  author = {John D. Beasley}
}

@BOOK{Ber00,
  title = {The Dots and Boxes Game: Sophisticated Child's Play},
  publisher = {A. K. Peter's Ltd.},
  year = {2000},
  author = {Elwyn Berlekamp}
}

@BOOK{BW94,
  title = {Mathematical Go: Chilling Gets the Last Point},
  publisher = {A. K. Peters, Ltd.},
  year = {1994},
  author = {Elwyn Berlekamp and David Wolfe}
}

@BOOK{BCG82,
  title = {Winning Ways},
  publisher = {Academic Press},
  year = {1982},
  author = {Elwyn R. Berlekamp and John H. Conway and Richard K. Guy},
  address = {London}
}

@INPROCEEDINGS{BDD+02,
  author = {Therese C. Biedl and Erik D. Demaine and Martin L. Demaine and Rudolf
	Fleischer and Lars Jacobsen and J. Ian Munro},
  title = {The Complexity of {C}lickomania},
  booktitle = {More Games of No Chance},
  year = {2002},
  editor = {R. J. Nowakowski},
  pages = {389--404},
  publisher = {Cambridge University Press},
  note = {Collection of papers from the MSRI Combinatorial Game Theory Research
	Workshop, Berkeley, California, July 2000.}
}

@ARTICLE{Bou02,
  author = {Charles L. Bouton},
  title = {Nim, a game with a complete mathematical theory},
  journal = {Annals of Mathematics\rm, Series 2},
  year = {1901--02},
  volume = {3},
  pages = {35--39}
}

@MISC{BOS94,
  author = {David Bremner and Joseph O'Rourke and Thomas Shermer},
  title = {Motion planning amidst movable square blocks is {PSPACE} complete},
  howpublished = {Draft},
  month = {June},
  year = {1994}
}

@ARTICLE{BW70,
  author = {John Bruno and Louis Weinberg},
  title = {A constructive graph-theoretic solution of the {S}hannon switching
	game},
  journal = {IEEE Transactions on Circuit Theory CT-17},
  year = {1970},
  volume = {1},
  pages = {74--81},
  month = {February}
}

@INPROCEEDINGS{Bur00,
  author = {Michael Buro},
  title = {Simple {A}mazons endgames and their connection to {H}amilton circuits
	in cubic subgrid graphs},
  booktitle = {Proceedings of the 2nd International Conference on Computers and
	Games},
  year = {2000},
  series = {Lecture Notes in Computer Science},
  address = {Hamamatsu, Japan},
  month = {October},
  note = {To appear}
}

@ARTICLE{CFS97,
  author = {Anne Condon and Joan Feigenbaum and Carsten Lund Peter Shor},
  title = {Random debaters and the hardness of approximating stochastic functions},
  journal = {SIAM Journal on Computing},
  year = {1997},
  volume = {26},
  pages = {369--400},
  number = {2}
}

@INPROCEEDINGS{Con96,
  author = {John H. Conway},
  title = {The Angel Problem},
  booktitle = {Games of No Chance},
  year = {1996},
  editor = {R. J. Nowakowski},
  pages = {1--12},
  publisher = {Cambridge University Press}
}

@ARTICLE{Con77,
  author = {J. H. Conway},
  title = {All games bright and beautiful},
  journal = {American Mathematical Monthly},
  year = {1977},
  volume = {84},
  pages = {417--434}
}

@BOOK{Con76,
  title = {On Numbers and Games},
  publisher = {Academic Press},
  year = {1976},
  author = {John H. Conway},
  address = {London}
}

@INPROCEEDINGS{Cul98,
  author = {Joseph Culberson},
  title = {Sokoban is {PSPACE}-complete},
  booktitle = {Proceedings of the International Conference on Fun with Algorithms},
  year = {1998},
  pages = {65--76},
  address = {Elba, Italy},
  month = {June}
}

@INPROCEEDINGS{DDE02,
  author = {Erik D. Demaine and Martin L. Demaine and David Eppstein},
  title = {Phutball Endgames are {NP}-hard},
  booktitle = {More Games of No Chance},
  year = {2002},
  editor = {R. J. Nowakowski},
  pages = {351--360},
  publisher = {Cambridge University Press},
  note = {Collection of papers from the MSRI Combinatorial Game Theory Research
	Workshop, Berkeley, California, July 2000. \url{http://www.arXiv.org/abs/cs.CC/0008025}}
}

@INPROCEEDINGS{DDO00a,
  author = {Erik D. Demaine and Martin L. Demaine and Joseph O'Rourke},
  title = {{PushPush} and {Push}-1 are {NP}-hard in {2D}},
  booktitle = {Proceedings of the 12th Annual Canadian Conference on Computational
	Geometry},
  year = {2000},
  pages = {211--219},
  address = {Fredericton, Canada},
  month = {August},
  note = {\url{http://www.cs.unb.ca/conf/cccg/eProceedings/26.ps.gz}}
}

@TECHREPORT{DDO00b,
  author = {Erik D. Demaine and Martin L. Demaine and Joseph O'Rourke},
  title = {{PushPush} is {NP}-hard in {2D}},
  institution = {Department of Computer Science, Smith College},
  year = {2000},
  number = {065},
  address = {Northampton, MA},
  month = {January},
  note = {\url{http://arXiv.org/abs/cs.CG/0001019}}
}

@INPROCEEDINGS{DDV00,
  author = {Erik D. Demaine and Martin L. Demaine and Helena Verrill},
  title = {Coin-Moving Puzzles},
  booktitle = {MSRI Combinatorial Game Theory Research Workshop},
  year = {2000},
  address = {Berkeley, California},
  month = {July}
}

@INPROCEEDINGS{DH01,
  author = {Erik D. Demaine and Michael Hoffmann},
  title = {Pushing Blocks is {NP}-Complete for Noncrossing Solution Paths},
  booktitle = {Proceedings of the 13th Canadian Conference on Computational Geometry},
  year = {2001},
  pages = {65--68},
  address = {Waterloo, Canada},
  month = {August},
  note = {\url{http://compgeo.math.uwaterloo.ca/~cccg01/proceedings/ long/eddemaine-24711.ps}}
}

@INPROCEEDINGS{DO92,
  author = {Arundhati Dhagat and Joseph O'Rourke},
  title = {Motion planning amidst movable square blocks},
  booktitle = {Proceedings of the 4th Canadian Conference on Computational Geometry},
  year = {1992},
  pages = {188--191}
}

@ARTICLE{DZ99,
  author = {Dorit Dor and Uri Zwick},
  title = {{SOKOBAN} and other motion planning problems},
  journal = {Computational Geometry: Theory and Applications},
  year = {1999},
  volume = {13},
  pages = {215--228},
  number = {4}
}

@BOOK{DF97,
  title = {Parameterized Complexity},
  publisher = {Springer-Verlag},
  year = {1997},
  author = {R. G. Downey and M. R. Fellows}
}

@MISC{Epp,
  author = {David Eppstein},
  title = {Computational Complexity of Games and Puzzles},
  note = {\url{http://www.ics.uci.edu/~eppstein/cgt/hard.html}}
}

@ARTICLE{Epp87,
  author = {David Eppstein},
  title = {On the {NP}-Completeness of Cryptarithms},
  journal = {SIGACT News},
  year = {1987},
  volume = {18},
  pages = {38--40},
  number = {3}
}

@INPROCEEDINGS{Eri96,
  author = {Jeff Erickson},
  title = {New {T}oads and {F}rogs Results},
  booktitle = {Games of No Chance},
  year = {1996},
  editor = {R. J. Nowakowski},
  pages = {299--310},
  publisher = {Cambridge University Press}
}

@ARTICLE{ET76,
  author = {S. Even and R. E. Tarjan},
  title = {A Combinatorial Problem Which Is Complete in Polynomial Space},
  journal = {Journal of the Association for Computing Machinery},
  year = {1976},
  volume = {23},
  pages = {710--719},
  number = {4}
}

@ARTICLE{Fer84,
  author = {Thomas S. Ferguson},
  title = {Mis\`{e}re Annihilation Games},
  journal = {Journal of Combinatorial Theory\rm, Series A},
  year = {1984},
  volume = {37},
  pages = {205--230}
}

@ARTICLE{Fer74,
  author = {T. S. Ferguson},
  title = {On Sums of Graph Games with Last Player Losing},
  journal = {International Journal of Game Theory},
  year = {1974},
  volume = {3},
  pages = {159--167},
  number = {3}
}

@ARTICLE{FB02,
  author = {Gary William Flake and Eric B. Baum},
  title = {\emph{{R}ush {H}our} is {PSPACE}-complete, or ``{W}hy you should
	generously tip parking lot attendants''},
  journal = {Theoretical Computer Science},
  year = {2002},
  volume = {270},
  pages = {895--911},
  number = {1--2},
  month = {January}
}

@INPROCEEDINGS{Fra96,
  author = {Aviezri S. Fraenkel},
  title = {Scenic Trails Ascending from Sea-Level {N}im to Alpine {C}hess},
  booktitle = {Games of No Chance},
  year = {1996},
  editor = {R. J. Nowakowski},
  pages = {13--42},
  publisher = {Cambridge University Press}
}

@ARTICLE{Fra94,
  author = {Aviezri S. Fraenkel},
  title = {Combinatorial Games: Selected Bibliography with a Succinct Gourmet
	Introduction},
  journal = {Electronic Journal of Combinatorics},
  year = {1994},
  note = {Dynamic Survey DS2, \url{http://www.combinatorics.org/Surveys/}.
	One version also appears in \emph{Games of No Chance}, pages~493--537,
	1996.}
}

@INPROCEEDINGS{Fra74,
  author = {Aviezri S. Fraenkel},
  title = {Combinatorial games with an annihilation rule},
  booktitle = {The Influence of Computing on Mathematical and Research and Education},
  year = {1974},
  volume = {20},
  series = {Proceedings of the Symposia in Applied Mathematics},
  pages = {87--91}
}

@INPROCEEDINGS{FGJ+78,
  author = {A. S. Fraenkel and M. R. Garey and D. S. Johnson and T. Schaefer
	and Y. Yesha},
  title = {The Complexity of Checkers on an {$N \times N$} Board - Preliminary
	Report},
  booktitle = {Proceedings of the 19th Annual Symposium on Foundations of Computer
	Science},
  year = {1978},
  pages = {55--64},
  address = {Ann Arbor, Michigan},
  month = {October}
}

@ARTICLE{FG87,
  author = {Aviezri S. Fraenkel and Elisheva Goldschmidt},
  title = {{PSPACE}-Hardness of Some Combinatorial Games},
  journal = {Journal of Combinatorial Theory\rm, Series A},
  year = {1987},
  volume = {46},
  pages = {21--38}
}

@ARTICLE{FL81,
  author = {Aviezri S. Fraenkel and David Lichtenstein},
  title = {Computing a Perfect Strategy for $n \times n$ Chess Requires Time
	Exponential in $n$},
  journal = {Journal of Combinatorial Theory\rm, Series A},
  year = {1981},
  volume = {31},
  pages = {199--214}
}

@ARTICLE{FY82,
  author = {A. S. Fraenkel and Y. Yesha},
  title = {Theory of Annihilation Games---{I}},
  journal = {Journal of Combinatorial Theory\rm, Series B},
  year = {1982},
  volume = {33},
  pages = {60--86}
}

@ARTICLE{FY79,
  author = {A. S. Fraenkel and Y. Yesha},
  title = {Complexity of problems in games, graphs and algebraic equations},
  journal = {Discrete Applied Mathematics},
  year = {1979},
  volume = {1},
  pages = {15--30}
}

@ARTICLE{FY76,
  author = {A. S. Fraenkel and Y. Yesha},
  title = {Theory of Annihilation Games},
  journal = {Bulletin of the American Mathematical Society},
  year = {1976},
  volume = {82},
  pages = {775--777},
  number = {5},
  month = {September}
}

@INCOLLECTION{Gar86,
  author = {Martin Gardner},
  title = {Cram, bynum and quadraphage},
  booktitle = {Knotted Doughnuts and Other Mathematical Entertainments},
  publisher = {W. H. Freeman and Company},
  year = {1986},
  chapter = {16}
}

@BOOK{GJ79,
  title = {Computers and Intractability: {A} Guide to the Theory of {NP}-Completeness},
  publisher = {W. H. Freeman \& Co.},
  year = {1979},
  author = {Michael R. Garey and David S. Johnson}
}

@ARTICLE{GR95,
  author = {Arthur S. Goldstein and Edward M. Reingold},
  title = {The complexity of pursuit on a graph},
  journal = {Theoretical Computer Science},
  year = {1995},
  volume = {143},
  pages = {93--112}
}

@BOOK{Gon86,
  title = {An Introduction to the Theory of Surreal Numbers},
  publisher = {Cambridge University Press},
  year = {1986},
  author = {Harry Gonshor}
}

@ARTICLE{Gru39,
  author = {P. M. Grundy},
  title = {Mathematics and Games},
  journal = {Eureka},
  year = {1939},
  volume = {2},
  pages = {6--8},
  month = {October},
  note = {Reprinted in \emph{Eureka: The Archimedeans' Journal}, 27:9--11,
	October 1964.}
}

@ARTICLE{GS56a,
  author = {P. M. Grundy and C. A. B. Smith},
  title = {Disjunctive games with the last player losing},
  journal = {Proceedings of the Cambridge Philosophical Society},
  year = {1956},
  volume = {52},
  pages = {527--533}
}

@INPROCEEDINGS{Guy96,
  author = {Richard K. Guy},
  title = {Unsolved Problems in Combinatorial Games},
  booktitle = {Games of No Chance},
  year = {1996},
  editor = {R. J. Nowakowski},
  pages = {475--491},
  publisher = {Cambridge University Press}
}

@ARTICLE{GS56b,
  author = {Richard K. Guy and Cedric A. B. Smith},
  title = {The {$G$}-values of various games},
  journal = {Proceedings of the Cambridge Philosophical Society},
  year = {1956},
  volume = {52},
  pages = {514--526}
}

@INPROCEEDINGS{Hof00,
  author = {Michael Hoffmann},
  title = {Push-\texttt{*} is {NP}-hard},
  booktitle = {Proceedings of the 12th Canadian Conference on Computational Geometry},
  year = {2000},
  pages = {205--210},
  address = {Fredericton, Canada},
  month = {August},
  note = {\url{http://www.cs.unb.ca/conf/cccg/eProceedings/13.ps.gz}}
}

@BOOK{Hor86,
  title = {Sliding Piece Puzzles},
  publisher = {Oxford University Press},
  year = {1986},
  author = {Edward Hordern}
}

@ARTICLE{IK94,
  author = {Shigeki Iwata and Takumi Kasai},
  title = {The {O}thello game on an $n \times n$ board is {PSPACE}-complete},
  journal = {Theoretical Computer Science},
  year = {1994},
  volume = {123},
  pages = {329--340}
}

@ARTICLE{Kay00a,
  author = {Richard Kaye},
  title = {Minesweeper is {NP}-Complete},
  journal = {Mathematical Intelligencer},
  year = {2000},
  volume = {22},
  pages = {9--15},
  number = {2}
}

@MISC{Kay00b,
  author = {Richard Kaye},
  title = {Infinite versions of minesweeper are {T}uring-complete},
  howpublished = {Manuscript},
  month = {August},
  year = {2000},
  note = {\url{http://www.mat.bham.ac.uk/R.W.Kaye/minesw/infmsw.pdf}}
}

@BOOK{Knu74,
  title = {Surreal Numbers},
  publisher = {Addison-Wesley},
  year = {1974},
  author = {Donald Knuth},
  address = {Reading, Mass.}
}

@INPROCEEDINGS{LMR00,
  author = {Michael Lachmann and Cristopher Moore and Ivan Rapaport},
  title = {Who Wins Domineering on Rectangular Boards?},
  booktitle = {MSRI Combinatorial Game Theory Research Workshop},
  year = {2000},
  address = {Berkeley, California},
  month = {July}
}

@ARTICLE{LS80,
  author = {David Lichtenstein and Michael Sipser},
  title = {{GO} is Polynomial-Space Hard},
  journal = {Journal of the Association for Computing Machinery},
  year = {1980},
  volume = {27},
  pages = {393--401},
  number = {2},
  month = {April}
}

@INPROCEEDINGS{ME01,
  author = {Cristopher Moore and David Eppstein},
  title = {One-Dimensional Peg Solitaire, and Duotaire},
  booktitle = {More Games of No Chance},
  year = {2001},
  editor = {R. J. Nowakowski},
  publisher = {Cambridge University Press},
  note = {To appear}
}

@INPROCEEDINGS{NP96,
  author = {Richard J. Nowakowski and David G. Poole},
  title = {Geography Played on Products of Directed Cycles},
  booktitle = {Games of No Chance},
  year = {1996},
  editor = {R. J. Nowakowski},
  pages = {329--337},
  publisher = {Cambridge University Press}
}

@TECHREPORT{OS99,
  author = {Joseph O'Rourke and {the} {Smith Problem Solving Group}},
  title = {{PushPush} is {NP}-hard in {3D}},
  institution = {Department of Computer Science, Smith College},
  year = {1999},
  number = {064},
  address = {Northampton, MA},
  month = {November},
  note = {\url{http://arXiv.org/abs/cs/9911013}}
}

@INPROCEEDINGS{Pap01,
  author = {Christos H. Papadimitriou},
  title = {Algorithms, Games, and the {I}nternet},
  booktitle = {Proceedings of the 33rd Annual ACM Symposium on Theory of Computing},
  year = {2001},
  address = {Crete, Greece},
  month = {July}
}

@ARTICLE{RW90,
  author = {Daniel Ratner and Manfred Warmuth},
  title = {The $(n^2-1)$-Puzzle and Related Relocation Problems},
  journal = {Journal of Symbolic Computation},
  year = {1990},
  volume = {10},
  pages = {111--137}
}

@ARTICLE{Rei81,
  author = {Stefan Reisch},
  title = {Hex ist {PSPACE}-vollst\"{a}ndig ({H}ex is {PSPACE}-complete)},
  journal = {Acta Informatica},
  year = {1981},
  volume = {15},
  pages = {167--191}
}

@ARTICLE{Rei80,
  author = {Stefan Reisch},
  title = {Gobang ist {PSPACE}-vollst\"{a}ndig ({G}obang is {PSPACE}-complete)},
  journal = {Acta Informatica},
  year = {1980},
  volume = {13},
  pages = {59--66}
}

@ARTICLE{RM78,
  author = {Edward Robertson and Ian Munro},
  title = {{NP}-completeness, puzzles and games},
  journal = {Utilitas Mathematica},
  year = {1978},
  volume = {13},
  pages = {99--116}
}

@ARTICLE{Rob84,
  author = {J. M. Robson},
  title = {{$N$} by {$N$} {C}heckers is {EXPTIME} complete},
  journal = {SIAM Journal on Computing},
  year = {1984},
  volume = {13},
  pages = {252--267},
  number = {2},
  month = {May}
}

@INPROCEEDINGS{Rob83,
  author = {J. M. Robson},
  title = {The complexity of {G}o},
  booktitle = {Proceedings of the IFIP 9th World Computer Congress on Information
	Processing},
  year = {1983},
  pages = {413--417}
}

@ARTICLE{Sav70,
  author = {Walter J. Savitch},
  title = {Relationships between nondeterministic and deterministic tape complexities},
  journal = {Journal of Computer and System Sciences},
  year = {1970},
  volume = {4},
  pages = {177--192},
  number = {2}
}

@ARTICLE{Sch78,
  author = {Thomas J. Schaefer},
  title = {On the Complexity of Some Two-Person Perfect-Information Games},
  journal = {Journal of Computer and System Sciences},
  year = {1978},
  volume = {16},
  pages = {185--225}
}

@ARTICLE{Smi66,
  author = {Cedric A. B. Smith},
  title = {Graphs and Composite Games},
  journal = {Journal of Combinatorial Theory},
  year = {1966},
  volume = {1},
  pages = {51--81}
}

@ARTICLE{Spr36,
  author = {R. Sprague},
  title = {{\"Uber mathematische Kampfspiele}},
  journal = {T\^ohoku Mathematical Journal},
  year = {1935--36},
  volume = {41},
  pages = {438--444}
}

@ARTICLE{SC79,
  author = {Larry J. Stockmeyer and Ashok K. Chandra},
  title = {Provably Difficult Combinatorial Games},
  journal = {SIAM Journal on Computing},
  year = {1979},
  volume = {8},
  pages = {151--174},
  number = {2}
}

@ARTICLE{Sto79,
  author = {W. E. Story},
  title = {Note on the `15' puzzle},
  journal = {American Mathematical Monthly},
  year = {1879},
  volume = {2},
  pages = {399--404}
}

@ARTICLE{UI90,
  author = {Ryuhei Uehara and Shigeki Iwata},
  title = {Generalized {Hi-Q} is {NP}-complete},
  journal = {Transactions of the IEICE},
  year = {1990},
  volume = {E73},
  pages = {270--273},
  month = {February}
}

@MISC{VrV01,
  author = {Sven de Vries and Rakesh Vohra},
  title = {Combinatorial Auctions: {A} Survey},
  howpublished = {Manuscript},
  month = {January},
  year = {2001},
  note = {\url{http://www-m9.ma.tum.de/~devries/}\allowbreak \url{comb_auction_supplement/comauction.pdf}}
}

@ARTICLE{Wil91,
  author = {Gordon Wilfong},
  title = {Motion planning in the presence of movable obstacles},
  journal = {Annals of Mathematics and Artificial Intelligence},
  year = {1991},
  volume = {3},
  pages = {131--150},
  number = {1}
}

@ARTICLE{Wil74,
  author = {Richard M. Wilson},
  title = {Graph Puzzles, Homotopy, and the Alternating Group},
  journal = {Journal of Combinatorial Theory\rm, Series B},
  year = {1974},
  volume = {16},
  pages = {86--96}
}

@INPROCEEDINGS{Wol01,
  author = {David Wolfe},
  title = {Go Endgames are {PSPACE}-hard},
  booktitle = {More Games of No Chance},
  year = {2001},
  editor = {R. J. Nowakowski},
  publisher = {Cambridge University Press},
  note = {To appear}
}

@BOOK{Wol94,
  title = {Cellular Automata and Complexity: Collected Papers},
  publisher = {Perseus Press},
  year = {1994},
  author = {Stephen Wolfram}
}

@ARTICLE{YTK+01,
  author = {Masaya Yokota and Tatsuie Tsukiji and Tomohiro Kitagawa and Gembu
	Morohashi and Shigeki Iwata},
  title = {Exptime-completeness of Generalized {T}sume-{S}hogi (in {J}apanese)},
  journal = {Transactions of the IEICE},
  year = {2001},
  volume = {J84-D-I},
  pages = {239--246},
  number = {3}
}

